package org.example.graph_theory;

import java.util.*;

public class Network_delay_time {
    public static void main(String[] args) {
        //网络延迟时间

        //有 n 个网络节点，标记为 1 到 n。
        //给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
        //现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1
//        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int[][] times = {{1,2,1},{1,3,4},{2,3,2},{2,4,5},{2,6,4},{3,4,2},{4,5,3},{5,7,4},{6,7,9}};
        int n = 7, k = 1;
        int i = networkDelayTime(times, n, k);
        System.out.println(i);
    }

    public static int networkDelayTime(int[][] times, int n, int k) {
        int[] minDist = new int[n+1];
        Arrays.fill(minDist,Integer.MAX_VALUE);

        HashSet<Integer> visited = new HashSet<>();

        minDist[k] = 0;

        while(k != -1){
            for (int i = 0; i < times.length; i++) {
                int from = times[i][0],to=times[i][1],weight=times[i][2];
                if (from == k){
                    minDist[to] = Math.min(minDist[to],minDist[from] + weight);
                }
            }

            visited.add(k);
            k = -1;
            int len = Integer.MAX_VALUE;

            for (int i = 1; i < minDist.length; i++) {
                if (!visited.contains(i) && len > minDist[i]){
                    len = minDist[i];
                    k = i;
                }
            }

        }

        int maxT = -1;
        for (int i = 1; i < minDist.length; i++) {
            maxT = Math.max(maxT,minDist[i]);
        }
        return visited.size() == n ? maxT : -1;
    }
}
